\section{快速排序代码示例}

\label{codes:quicksort}


相关原理参考\label{summary:quicksort}。

\begin{lstlisting}[language=C]

/* Simplest version, Lomuto partitioning */
void qsort1(int l, int u)
{	int i, m;
	if (l >= u)
		return;
	m = l;
	for (i = l+1; i <= u; i++)
		if (x[i] < x[l])
			swap(++m, i);
	swap(l, m);
	qsort1(l, m-1);
	qsort1(m+1, u);
}
\end{lstlisting}

\begin{lstlisting}[language=C]
/* Sedgewick's version of Lomuto, with sentinel */
void qsort2(int l, int u)
{	int i, m;
	if (l >= u)
		return;
	m = i = u+1;
	do {
		do i--; while (x[i] < x[l]);
		swap(--m, i);
	} while (i > l);
	qsort2(l, m-1);
	qsort2(m+1, u);
}
\end{lstlisting}


\begin{lstlisting}[language=C]
/* Two-way partitioning */
void qsort3(int l, int u)
{	int i, j;
	DType t;
	if (l >= u)
		return;
	t = x[l];
	i = l;
	j = u+1;
	for (;;) {
		do i++; while (i <= u && x[i] < t);
		do j--; while (x[j] > t);
		if (i > j)
			break;
		swap(i, j);
	}
	swap(l, j);
	qsort3(l, j-1);
	qsort3(j+1, u);
}
\end{lstlisting}


\begin{lstlisting}[language=C]
/* qsort3 + randomization + isort small subarrays + swap inline */
int cutoff = 50;
void qsort4(int l, int u)
{	int i, j;
	DType t, temp;
	if (u - l < cutoff)
		return;
	swap(l, randint(l, u));
	t = x[l];
	i = l;
	j = u+1;
	for (;;) {
		do i++; while (i <= u && x[i] < t);
		do j--; while (x[j] > t);
		if (i > j)
			break;
		temp = x[i]; x[i] = x[j]; x[j] = temp;
	}
	swap(l, j);
	qsort4(l, j-1);
	qsort4(j+1, u);
}

\end{lstlisting}

\cite{sedgewick}提出了三路分割，用于应对有大量keys重复的情形，并证明三路分割的快速排序具有熵最优性。该算法使用了$(2lg2)NH$次比较，H为香农熵，$H=-\sum{p_{k}lnp_k}$。


\begin{lstlisting}[language=Java]

public class Quick3way
{
    private static void sort(Comparable[] a, int lo, int hi)
    { // See page 289 for public sort() that calls this method.
	if (hi <= lo) return;
	int lt = lo, i = lo+1, gt = hi;
	Comparable v = a[lo];
	while (i <= gt)
	{
	    int cmp = a[i].compareTo(v);
	    if (cmp < 0) exch(a, lt++, i++);
	    else if (cmp > 0) exch(a, i, gt--);
	    else
	    i++;
	} // Now a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
	sort(a, lo, lt - 1);
	sort(a, gt + 1, hi);
    }
}
\end{lstlisting}


